package exercises.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/pascals-triangle/">
 * 118. 杨辉三角</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * <p>
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 *
 * @author or2
 * @date 2021年09月22日 时间: 9:08
 */
public class No118 {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();

        ans.add(new ArrayList<>(List.of(1)));
        if (numRows == 1) {
            return ans;
        }

        ans.add(new ArrayList<>(List.of(1, 1)));
        if (numRows == 2) {
            return ans;
        }

        for (int i = 2; i < numRows; i++) {
            ArrayList<Integer> layer = new ArrayList<>();
            layer.add(1);
            List<Integer> lastList = ans.get(i - 1);
            for (int j = 1; j <= i - 1; j++) {
                layer.add(lastList.get(j - 1) + lastList.get(j));
            }
            layer.add(1);
            ans.add(layer);
        }

        return ans;
    }
}
